
/*
回溯
连接：https://leetcode.cn/problems/number-of-islands/description/
题目：岛屿数量

  
算法思路：
遍历整个矩阵，每次找到「⼀块陆地」的时候：
• 说明找到「⼀个岛屿」，记录到最终结果 ret ⾥⾯；
• 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次
遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。
• 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是 733. 图像渲染 这道题~
这样，当我们，遍历完全部的矩阵的时候， ret 存的就是最终结果。
解法（dfs）：
算法流程：
1. 初始化 ret = 0 ，记录⽬前找到的岛屿数量;
2. 双重循环遍历⼆维⽹格，每当遇到⼀块陆地，标记这是⼀个新的岛屿，然后将这块陆地相连的陆地
全部变成海洋。
递归函数的设计：
1. 把当前格⼦标记为⽔；
2. 向上、下、左、右四格递归寻找陆地，只有在下标位置合理的情况下，才会进⼊递归：
a. 下⼀个位置的坐标合理；
b. 并且下⼀个位置是陆地

   
    
*/
class Solution {
public:
    int ret;
    vector<vector<bool>> vis;
    int m,n;
    int r[4] = {0,0,-1,1};
    int c[4] = {-1,1,0,0};
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vis = vector<vector<bool>>(m,vector<bool>(n));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(!vis[i][j] && grid[i][j]=='1')
                {
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>>& grid,int i,int j)
    {
        vis[i][j] = true;
        for(int k=0;k<4;k++)
        {
            int x = i+r[k];
            int y = j+c[k];
            if(x>=0 && x<m && y>=0 && y<n && vis[x][y] == false &&grid[i][j]=='1' )
            {
                dfs(grid,x,y);
            }
        }
    }
};